Concurrent programs may include multiple threads or processes separately executing sections or blocks of code as part of the program that allows multiple tasks to be executed in parallel. This may result in race conditions in which different threads or processes make modifications to a common memory location represented by a shared data structure. The modifications to the shared data structure are done by executing software routines which access the shared data structure. These software routines may be referred to as a critical section or block of code. Modifications to the shared data structure may leave the shared data structure in an inconsistent state and may not produce the expected result during the execution of the program.
Synchronization may be a technique to prevent a race condition in which multiple threads or processes cooperate with each other for executing the critical section of code and only one thread or process executes the critical section at a time. Synchronization between threads may be achieved by a variety of techniques of which locking may be one of them. Mutually exclusive (mutex) is a type of lock in which a thread may be required to first acquire a lock on a mutex lock object before getting exclusive access to execute a critical section of code. The other threads may then need to acquire the lock on the mutex object before getting exclusive access to execute the critical section. For these examples, if the lock has already been acquired, a given thread may be configured to wait until the lock has been released on the mutex lock object before acquiring the lock. The given thread may then lock the mutex lock object to execute the given critical section of code while locking out other threads. In some examples, after executing the critical section, the given thread or process holding the lock may release it. Other threads waiting to acquire the lock on the mutex lock object may then try to acquire the lock to execute the critical section.
Acquiring a lock on a mutex lock object and then releasing the lock is an example methodology to ensure synchronization between threads that may modify the shared data structure during execution of the critical section of code. However, lock contention between different threads may slow down or stall a multi-threaded program. As the number of threads for a given multi-threaded program increases so does the likelihood of lock contention.
Additionally there can be multiple types of modification of the shared data structure which can be related or unrelated depending on a nature of the application, components of the application, use cases involved or the shared data structure in question. Mutual exclusion of threads by locking mechanism for any type of modification of a given shared data structure that is achieved by executing the same or multiple critical sections of code or routines may sometimes cause unnecessary delay in program execution. The unnecessary delay may result in performance degradation of the application. In particular, performance degradation may occur for modification operations that may not be related to each other, do not cause shared data structure inconsistency or induce an acceptable amount of shared data structure inconsistency.
Also, similar or different types of modifications to the shared data structure may occur within different execution conditions or environment settings. These modifications of the shared data structure under different environment setting or contexts may or may not be related to each other. In other words, concurrent modification of the shared data structure may or may not leave it in inconsistent situation under different contexts. Hence, concurrent modifications of the shared data structure may purely depend on a nature of an application or components of the application, use cases involved, the shared data structure in question as to what level of synchronization between different threads may be needed in different execution contexts.